// 给定两个没有重复元素的数组nums1和nums2，其中nums1是nums2的子集，要求找出nums1中每个元素在nums2中下一个比其大的值

// 思路：使用单调递增栈，因为nums1是nums2的子集，所以我们可以先遍历一遍nums2，并构造单调递增栈，求出nums2中每个元素右侧更大的元素，然后存储到哈希表中
// 再遍历一遍nums1，从哈希表中取出对应结果
// 1. stack表示单调递增栈，哈希表num_map表示nums2中下一个比当前元素大的数值，映射关系为 当前元素值 -》 下一个比当前元素大的数值
// 2. 遍历数组nums2，对于当前元素
//  如果当前元素较小，则直接让当前元素入栈
//  如果当前元素较大，则一直出栈，直到当前元素小于栈顶元素
//     出栈时，出栈元素是第一个大于当前元素值的元素，则将其映射到num_map中
// 3.  遍历完数组nums2，完成映射后，再遍历数组nums1
// 4. 从num_map中取出对应的值，将其加入到答案数组中
const Stack  = require('../1. 堆栈基础/1. 堆栈的顺序存储实现')
function nextGreaterElement(nums1, nums2) {
    let res = []
    let stack = new Stack()
    let num_map = {}
    for (let i = 0; i < nums2.length; i++) {
        while (!stack.isEmpty() && nums2[i] > stack.peek()) {
            num_map[stack.peek()] = nums2[i]
            stack.pop()
        }
        stack.push(nums2[i])
    }
    for (let i = 0; i < nums1.length; i++) {
        res.push(num_map[nums1[i]] || -1)
    }
    return res
}

let nums1 = [4, 1, 2]
let nums2 = [1, 3, 4, 2, 5]
console.log(nextGreaterElement(nums1, nums2));